package algorithm.dynamic;

/**
 * LeetCode : https://leetcode.com/problems/maximal-square/
 * Difficulty : Medium
 *
 * 题目：
 * 给一个int二维数组，数组中只有0和1两种数字。
 * 找出其中只有1的最大的正方形，返回其面积.
 *
 * 思路：动态规划
 * 数组中数字存储以当前节点为右下角的正方形的边长。再额外一个字段，存储已经遇到过的最大的边长。
 * 面积结果就是 边长*边长
 *
 *
 * 具体步骤：
 * 逐个遍历二维数组，如果当前节点值=='1'，则说明可能是一个正方形的右下角。进入判断逻辑
 * 判断逻辑：
 *  取左，上，以及左上对角。三个节点的数字。取其中最低的数字min。那么当前节点的值就是min+1.
 *  例如：
 *  左=1，上=0，左上=1。那么这样是组不成正方形的。此时min=0, 那么当前节点值就是1.
 *  代表以当前节点为右下角的正方形边长是1
 *
 *  左=1，上=2，左上=1。那么此时min=1，可以组成正方形当前节点值为2.
 *  即，当前节点为右下角的正方形，边长为2
 *
 * @Author Antony
 * @Since 2018/10/31 11:23
 */
public class MaximalSquare {

    public static void main(String[] args) {
        char[][] matrix = new char[4][5];
        matrix[0] = new char[]{'1','0','1','0','0'};
        matrix[1] = new char[]{'1','0','1','1','1'};
        matrix[2] = new char[]{'1','1','1','1','1'};
        matrix[3] = new char[]{'1','0','0','1','0'};

        char[][] matrix_02 = new char[][]{{'0'}};

//        System.out.println(maximalSquare(matrix));
//        System.out.println(maximalSquare(matrix_02));
        System.out.println(maximalSquare_optimize(matrix));
        System.out.println(maximalSquare_optimize(matrix_02));
    }

    /**
     * Leetcode : run 8ms(beats 95.55%)
     * 注意：
     * 1) 要对数组判空，如果length==0 则直接返回0
     * 2) 注意这是char型数组，要对元素和数字做转换。
     * 2) 如果结果是0，则要对 maximalLength 的这个结果判0，如果不是0才转换为数字。
     *
     *
     * 该思路还存在的一个可能的漏洞：
     * java中char的可取范围是 0x0000 ~ 0xFFFF
     * 但是这个需要计算的结果是整数的，整形的范围是 0x00000000 ~ 0x7FFFFFFF
     * 如果存储的结果超过char的范围，那就会报错
     *
     * 相对该方法的优点：
     * 空间复杂度为O(1) 利用已有的数组，但是会修改原来数组的值
     *
     * @param matrix
     * @return
     */
    public static int maximalSquare(char[][] matrix){
        if(matrix.length==0){
            return 0;
        }
        int maximalLength = 0;
        int width = matrix[0].length;
        int height = matrix.length;
        int up,left,angles,min;
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(matrix[i][j] == '1'){
                    up = i-1>=0 ? matrix[i-1][j] : '0';
                    left = j-1>=0 ? matrix[i][j-1] : '0';
                    angles = i-1>=0&&j-1>=0 ? matrix[i-1][j-1] : '0';
                    min = Math.min(up,Math.min(left,angles));
                    min = min+1;
                    matrix[i][j] = (char) min;
                    maximalLength = min > maximalLength ? min : maximalLength;
                }
            }
        }
        maximalLength = maximalLength==0 ? 0 : maximalLength-'0';
        return maximalLength*maximalLength;
    }

    /**
     * leetcode : 9ms, 65.01%
     * 对上面思路的一个优化。
     * 新建一个int的二维数组。将结果存在该二维数组中。避免了char型值范围越界的问题。
     * 也简化了char 和 int 互转的问题
     *
     * (可能因为是新建了一个数组，所以速度慢了)
     * @param matrix
     * @return
     */
    public static int maximalSquare_optimize(char[][] matrix){
        if(matrix.length == 0){
            return 0;
        }
        int height = matrix.length;
        int width = matrix[0].length;
        int[][] matrixArray = new int[height][width];
        int maximalLength = 0;
        int up,left,angles,tmp;
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                tmp = 0;
                if(matrix[i][j] == '1'){
                    up = i>=1 ? matrixArray[i-1][j] : 0;
                    left = j>=1 ? matrixArray[i][j-1] : 0;
                    angles = i>=1&&j>=1 ? matrixArray[i-1][j-1] : 0;
                    tmp = Math.min(up,Math.min(left,angles));
                    tmp +=1;
                    maximalLength = tmp > maximalLength ? tmp : maximalLength;
                }
                matrixArray[i][j] = tmp;
            }
        }
        return maximalLength * maximalLength;
    }

}
